{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #训练计划 VI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: trainingPlan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #训练计划 VI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>教学过程中，教练示范一次，学员跟做三次。该过程被混乱剪辑后，记录于数组 <code>actions</code>，其中 <code>actions[i]</code> 表示做出该动作的人员编号。请返回教练的编号。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>actions = [5, 7, 5, 5]\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>actions = [12, 1, 6, 12, 6, 12, 6]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= actions.length &lt;= 10000</code></li>\n",
    "\t<li><code>1 &lt;= actions[i] &lt; 2^31</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,7,5,5]', '[12,1,6,12,6,12,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, nums):\n",
    "        # 获取数组中的最大值 max，并计算需要的最大二进制位数 k。\n",
    "        # 目的是优化循环次数，免得 32 个比特位全部计算\n",
    "        max_val = max(nums)\n",
    "        k = 0\n",
    "        while 2 ** k < max_val:\n",
    "            k += 1\n",
    "        ret = 0\n",
    "\n",
    "\n",
    "        for i in range(k+1):\n",
    "            cnt = 0\n",
    "            for j in range(len(nums)):\n",
    "                if i >= 1:\n",
    "                    nums[j] >>= 1\n",
    "                cnt += nums[j] & 1\n",
    "            if cnt % 3 != 0:\n",
    "                ret = ret | (1 <<  i)\n",
    "\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        counts = [0] * 32\n",
    "        for action in actions:\n",
    "            for i in range(32):\n",
    "                counts[i] += action & 1 # 更新第 i 位 1 的个数之和\n",
    "                action >>= 1            # 第 i 位 --> 第 i 位\n",
    "        res, m = 0, 3\n",
    "        for i in range(31, -1, -1):\n",
    "            res <<= 1\n",
    "            res |= counts[i] % m        # 恢复第 i 位\n",
    "        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, nums: List[int]) -> int:\n",
    "        tmp=[0]*32\n",
    "        for i in nums:\n",
    "            b=bin(i)[2:][::-1]\n",
    "            for j in range(len(b)):\n",
    "                tmp[j]+=int(b[j])\n",
    "        tmp=[str(x%3) for x in tmp]\n",
    "        return int(\"\".join(tmp[::-1]),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        bitSum = [0 for i in range(32)]\n",
    "        for item in actions:\n",
    "            bitMask = 1\n",
    "            for i in range(31,-1,-1):\n",
    "                if item & bitMask != 0:\n",
    "                    bitSum[i] += 1\n",
    "                bitMask <<= 1\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res <<= 1\n",
    "            res += bitSum[i] % 3\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, nums: List[int]) -> int:\n",
    "        counts = [0] * 32\n",
    "        for num in nums:\n",
    "            for j in range(32):\n",
    "                counts[j] += num & 1    # 更新第i位个数之和\n",
    "                num >>= 1               # 第i位 --> 第i+1位\n",
    "        print(counts)\n",
    "        res, m = 0, 3\n",
    "        for i in range(31, -1, -1):\n",
    "            res <<= 1\n",
    "            print(res)\n",
    "            res |= counts[i] % m\n",
    "        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(32):\n",
    "            bit=0\n",
    "            for action in actions:\n",
    "                bit+=((action>>i)&1)\n",
    "            res+=(bit%3)<<i\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        cnt = [0]*32\n",
    "        for a in actions:\n",
    "            for i in range(32):\n",
    "                if a & (1<<i):\n",
    "                    cnt[i] += 1\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if cnt[i]%3!=0:\n",
    "                res += 1<<i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        num_1 = [0] * 32\n",
    "        for a in actions:\n",
    "            i = 0\n",
    "            while a>0:\n",
    "                num_1[i] += (a&1)\n",
    "                a = a>>1\n",
    "                i += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            if num_1[i]%3==1:\n",
    "                ans = ans | (1<<i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, nums: List[int]) -> int:\n",
    "        counts = [0] * 32\n",
    "        for num in nums:\n",
    "            for j in range(32):\n",
    "                counts[j] += num & 1\n",
    "                num >>= 1\n",
    "        res, m = 0, 3\n",
    "        for i in range(32):\n",
    "            res <<= 1\n",
    "            res |= counts[31 - i] % m\n",
    "        return res if counts[31] % m == 0 else ~(res & 0xffffffff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        bits = [0] * 31\n",
    "        for a in actions:\n",
    "            temp = a\n",
    "            for i in range(31):\n",
    "                bits[i] += temp % 2\n",
    "                temp //= 2\n",
    "        coach, temp = 0, 1\n",
    "        for i in range(31):\n",
    "            if bits[i] % 3 != 0:\n",
    "                coach += temp\n",
    "            temp *= 2\n",
    "        return coach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        a = b = 0\n",
    "        for c in actions:\n",
    "            a, b = (~a & b & c) | (a & ~b & ~c), (~a & b & ~c) | (~a & ~b & c)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int: \n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        # 把所有数字都看成32位的二进制数\n",
    "        # 将数组中的所有数字相加，那么对于某一位来说，数值一定是3N或3N+1（所有出现3次的数字对该位置的贡献一定是0或3，出现一次的数字贡献一定是0或1）\n",
    "        # 对该位置的和用3取余，结果就是出现一次的数字在该位置的值。\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            cnt = 0\n",
    "            bit = 1 << i\n",
    "            for num in actions:\n",
    "                if num & bit != 0:\n",
    "                    cnt = cnt + 1\n",
    "            if cnt % 3 == 1:\n",
    "                res = res | bit\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions):\n",
    "        count = [0]*32\n",
    "\n",
    "        for num in actions:\n",
    "            m = 1\n",
    "            for i in range(32):\n",
    "                if num&m:\n",
    "                    count[i]+=1\n",
    "                m<<=1\n",
    "        res = 0\n",
    "        for i in range(len(count)):\n",
    "            res += (count[i]%3)<<i\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        counts = [0] * 32\n",
    "        for action in actions:\n",
    "            for i in range(32):\n",
    "                counts[i] += action & 1 # 更新第 i 位 1 的个数之和\n",
    "                action >>= 1            # 第 i 位 --> 第 i 位\n",
    "        res, m = 0, 3\n",
    "        for i in range(31, -1, -1):\n",
    "            res <<= 1\n",
    "            res |= counts[i] % m        # 恢复第 i 位\n",
    "        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        # 没有要求空间复杂度，直接哈希求解\n",
    "        # act_dict = defaultdict(int)\n",
    "        # for a in actions:\n",
    "        #     act_dict[a] += 1\n",
    "        \n",
    "        # for t in set(actions):\n",
    "        #     if act_dict[t] == 1:\n",
    "        #         return t\n",
    "        \n",
    "        # 排序求解，直接排序，然后重复元素会相邻\n",
    "\n",
    "        # 位运算求解\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        #时间复杂度：O(n)\n",
    "        #空间复杂度：O（1）\n",
    "        #第一步：记录每个位置1出现的次数\n",
    "        #counts记录的是从右向左开始记录的\n",
    "        #比如：第一个是最后一位出现1的个数\n",
    "        counts=[0]*32\n",
    "        for action in actions:\n",
    "            for i in range(32):\n",
    "                counts[i]+=action&1 \n",
    "                action>>=1\n",
    "        res=0\n",
    "        m=3\n",
    "        for i in range(31,-1,-1):\n",
    "            res<<=1\n",
    "            res|=counts[i]%m\n",
    "        if counts[-1]%m==0:\n",
    "            return res\n",
    "        else:\n",
    "            return ~(res^0xffffffff)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, nums: List[int]) -> int:\n",
    "        counter = Counter(nums)\n",
    "        for k, v in counter.items():\n",
    "            if v == 1: return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        # 有限状态自动机\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones\n",
    "\n",
    "        # 频率统计\n",
    "        f = defaultdict(int)\n",
    "        for i in actions:\n",
    "            f[i] += 1\n",
    "        for j in f:\n",
    "            if f[j]==1:\n",
    "                return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            cnt = 0\n",
    "            bit = 1 << i\n",
    "            for num in actions:\n",
    "                if num & bit != 0:\n",
    "                    cnt += 1\n",
    "            if cnt % 3 != 0:\n",
    "                res |= bit\n",
    "        return (res - 2 ** 31) if res > 2 ** 31 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def trainingPlan(self, nums: List[int]) -> int:\n",
    "          occ1 = set()\n",
    "          occ3 = set()\n",
    "          for num in nums:\n",
    "               if num in occ3:\n",
    "                    continue\n",
    "               elif num in occ1:\n",
    "                    occ1.remove(num)\n",
    "                    occ3.add(num)\n",
    "               else:\n",
    "                    occ1.add(num)\n",
    "          return occ1.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        res = [0] * 32\n",
    "\n",
    "        for num in actions:\n",
    "            for i in range(32):\n",
    "                if num & 1:\n",
    "                    res[i] += 1\n",
    "                num >>= 1\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(31, -1, -1):\n",
    "            ans <<= 1\n",
    "            ans |= res[j] % 3\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        num = {}\n",
    "        for i in actions:\n",
    "            if i not in num :\n",
    "                num[i] = 1\n",
    "            else :\n",
    "                num[i] += 1\n",
    "        for i, time in num.items():\n",
    "            if time == 1 :\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        li1 = sorted(actions)+[0,0]\n",
    "        if li1[0]!=li1[1]:\n",
    "            return li1[0]\n",
    "        else:\n",
    "            i = 0\n",
    "            while li1[i] ==li1[i+2]:\n",
    "                i+=3\n",
    "            else:\n",
    "                return li1[i]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0,0\n",
    "        for num in actions:\n",
    "            ones = ones ^ num & ~twos\n",
    "            twos = twos ^ num & ~ones\n",
    "        return ones\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        counts = [0] * 32\n",
    "        for action in actions:\n",
    "            for i in range(32):\n",
    "                counts[i] += action & 1 # 更新第 i 位 1 的个数之和\n",
    "                action >>= 1            # 第 i 位 --> 第 i 位\n",
    "        res, m = 0, 3\n",
    "        for i in range(31, -1, -1):\n",
    "            res <<= 1\n",
    "            res |= counts[i] % m        # 恢复第 i 位\n",
    "        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        one, two = 0, 0\n",
    "        for action in actions:\n",
    "            one = one ^ action & ~ two \n",
    "            two = two ^ action & ~ one \n",
    "        return one "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        action_map = {}\n",
    "        for action in actions:\n",
    "            action_map[action] = action_map.get(action, 0) + 1\n",
    "        for k, v in action_map.items():\n",
    "            if v == 1:\n",
    "                return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        counts = [0] * 32\n",
    "        for action in actions:\n",
    "            for i in range(32):\n",
    "                counts[i] += action & 1\n",
    "                action >>= 1\n",
    "        res, m = 0, 3\n",
    "        for i in range(31, -1, -1):\n",
    "            res <<= 1\n",
    "            res |= counts[i] % m\n",
    "        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        res=0\n",
    "        for i in range(32):\n",
    "            b=1<<i\n",
    "            count=0\n",
    "            for num in actions:\n",
    "                if num&b!=0:\n",
    "                    count+=1\n",
    "            if count%3!=0:\n",
    "                res+=b\n",
    "        return res if res&0x80000000==0 else res-0xffffffff#~(res^0xffffffff)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        n = len(actions)\n",
    "        for i in range(n):\n",
    "            if actions.count(actions[i]) == 1:\n",
    "                return actions[i]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for num in actions:\n",
    "            ones = ones ^ num & ~twos\n",
    "            twos = twos ^ num & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        mask  = 1\n",
    "        for _ in range(32):\n",
    "            i, j = 0, len(actions) - 1                \n",
    "            while i <= j:\n",
    "                ## Move 0 bit to left\n",
    "                if actions[i] & mask != 0:\n",
    "                    actions[i], actions[j] = actions[j], actions[i]\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    i += 1            \n",
    "                # print(actions)\n",
    "            \n",
    "            mask <<= 1\n",
    "\n",
    "            if (i % 3) == 1:\n",
    "                actions = actions[:i]\n",
    "            else:\n",
    "                actions = actions[i:]\n",
    "\n",
    "            # print(actions)\n",
    "            if len(actions) == 1:\n",
    "                return actions[0]\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            ones = ones ^ action & ~twos\n",
    "            twos = twos ^ action & ~ones\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for action in actions:\n",
    "            dic[action] += 1\n",
    "        for k, v in dic.items():\n",
    "            if v == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        \n",
    "        ones, twos = 0, 0\n",
    "        for action in actions:\n",
    "            twos |= ones & action\n",
    "            ones ^= action\n",
    "            common = ones & twos\n",
    "            ones &= ~common\n",
    "            twos &= ~common\n",
    "        return ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        n = len(actions)\n",
    "        mp = Counter(actions)\n",
    "        for a in actions:\n",
    "            if mp[a] == 1:\n",
    "                return a\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            cnt = 0\n",
    "            bit = 1 << i\n",
    "            for action in actions:\n",
    "                if action & bit != 0:\n",
    "                    cnt += 1\n",
    "            if cnt % 3 != 0:\n",
    "                res |= bit\n",
    "        return res - 2 ** 31 if res > 2 ** 31 - 1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        for i in actions:\n",
    "            if actions.count(i) == 1:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        cnt = [0] * 32 \n",
    "        for action in actions:\n",
    "            for i in range(32):\n",
    "                cnt[i] += action & 1\n",
    "                action >>= 1 \n",
    "        \n",
    "        res = 0 \n",
    "        for i in range(31, -1, -1):\n",
    "            res <<= 1 \n",
    "            res |= cnt[i] % 3 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        for i in range(len(actions)):\n",
    "            if actions.count(actions[i]) == 1:\n",
    "                return actions[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        o, t = 0, 0\n",
    "        for ac in actions:\n",
    "            o = o^ac&~t\n",
    "            t = t^ac&~o\n",
    "        return o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        # 频率统计\n",
    "        f = defaultdict(int)\n",
    "        for i in actions:\n",
    "            f[i] += 1\n",
    "        for j in f:\n",
    "            if f[j]==1:\n",
    "                return j "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        #时间复杂度：O(n)\n",
    "        #空间复杂度：O（1）\n",
    "        #第一步：记录每个位置1出现的次数\n",
    "        #counts记录的是从右向左开始记录的\n",
    "        #第一个是最后一位出现1的个数\n",
    "        counts=[0]*32\n",
    "        \n",
    "        for action in actions:\n",
    "            for i in range(32):\n",
    "                counts[i]+=action&1\n",
    "                action>>=1\n",
    "        res=0\n",
    "        m=3\n",
    "        for i in range(31,-1,-1):\n",
    "            res<<=1\n",
    "            res|=counts[i]%m \n",
    "        if counts[31]%m==0:\n",
    "            return res \n",
    "        else:\n",
    "            return ~(res^0xffffffff)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def trainingPlan(self, actions: List[int]) -> int:\n",
    "        map = {}\n",
    "        for i in actions:\n",
    "            if map.get(i, 0):\n",
    "                map[i] += 1\n",
    "            else:\n",
    "                map[i] = 1\n",
    "        for key, value in map.items():\n",
    "            if value == 1:\n",
    "                return key\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
